package baseclass.l_string;

/**
 * @date 2020/3/6 14:29
 */
public class Code05_LongestPalindRome {

    /**
     * 方式1：暴力遍历所有子串，然后对每个子串进行判定。
     * 时间O(n³)
     */
    public static String m1(String str) {
        if (str == null || str.length() <= 1) return str;
        String res = str.substring(0, 1);
        for (int i = 0; i < str.length(); i++) {
            for (int j = i; j < str.length(); j++) {
                if (isPalindRome(str, i, j)) {
                    if (j - i + 1 > res.length()) {
                        res = str.substring(i, j + 1);
                    }
                }
            }
        }
        return res;
    }

    private static boolean isPalindRome(String str, int i, int j) {
        while (i < j) {
            if (str.charAt(i++) != str.charAt(j--)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 方式2：对每个位置往左右两边扩，进行奇数偶数判断。
     * 时间O(2n²)
     */
    public static String m2(String str) {
        if (str == null || str.length() <= 1) return str;
        int start = 0;
        int end = 0; //end - start + 1
        //对每个位置i都往两遍扩，分奇数偶数判断是否是回文
        for (int i = 0; i < str.length(); i++) {
            int len1 = expand(str, i, i);
            int len2 = expand(str, i, i + 1);
            int len = Math.max(len1, len2);
            //如果是奇数扩充，i左右一边分一半
            //如果是偶数扩充，i左边分的比右边分的少一个
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;//如果是偶数少分一个，奇数分一半
                end = i + len / 2;//奇数偶数都分一半
            }
        }
        return str.substring(start,end+1);
    }
    /**
     * 方式3：把给定的字符串进行填充，必定是奇数。然后扩判断。
     * 时间O(n²)
     */
    public static String m3(String str) {
        if (str == null || str.length() <= 1) return str;
        StringBuilder sb = new StringBuilder();
        sb.append("#");
        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i)).append("#");
        }
        //如  aba - >  #a#b#a# ;   aa -> #a#a#
        //如果是奇数不影响，如果是偶数从中间#开始也不影响
        String str1 = sb.toString();
        int start = 0,end = 0;
        for (int i = 0; i < str1.length(); i++) {
            int len = expand(str1,i,i);
            if(len > end - start + 1){
                start = i - (len-1)/2;//都是奇回文，可以写成 i - len/2
                end = i + len/2;
            }
        }
        return str1.substring(start,end+1).replace("#","");
    }


    /**
     * 从i和j位置往两遍扩，判断是否是回文
     */
    private static int expand(String str, int i, int j) {
        while (i >= 0 && j < str.length() && str.charAt(i) == str.charAt(j)) {
            i--;
            j++;
        }
        //i+1和 j-1等
        i++;
        j--;
        return j - i + 1;
    }



    public static void main(String[] args) {
        String str = "ccccabbac";
        System.out.println(m1(str));
        System.out.println(m2(str));
        System.out.println(m3(str));
    }
}
